#1 Two Sum

medium版本

題目原文

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

題目網址

題目翻譯

• 給予一組數列nums
• 給予一個target目標值
• 從數列nums中找出兩個數字相加是target值
• 將兩個數字在數列中的位置回傳
• input數列只會找到一組可以合成target值的解(像是如果target=8則輸入數列不可能是[3,5,6,2]，因為有兩組解數字3和５，數字6和2)
• 每個數字不能重複使用(比如target=4，輸入數列[2,1,5]，不能將數字2使用二次來合成4)

解題思路

• 假設情境

  某次資料結構的期中考，老師因為太多同學常常翹課所以起賭爛，決定出一份超難的考卷，下定決心要當掉一半的人。聰明的小明，在那次考試中拿到60分(target)的成績，逃過被老師當掉的風險，但天生個性白爛的他，決定去取笑那些考得比他低的同學，要找兩個加起來才剛好和他分數一樣60分的同學取笑。小明知道同學都把考卷放在自己的置物櫃裡，因此決定要翻同學的櫃子，偷拿出他們的考卷來當面取笑。

• 暴力破解法(Brute Force)

  小明來到同學的櫃子，先開了第一個櫃子發現是自己平常很討厭的小華，只考了34分。小明很想取笑他，因此開始從第一個櫃子之後依序翻櫃子，要找出只有考26分的同學，用來取笑小華，但是後來將全部櫃子都看過一遍，卻發現全班沒有人考26分??，只好又以2號櫃子考33分的小美當基準，要找考27分的同學。由於他先前沒有紀錄每個櫃子的同學考幾分，因此又要重頭開始翻同學的櫃子，最後終於在第45號櫃子找到考27分的同學，偷出他們的考卷，卻也浪費一堆時間。

let twoSum = function(nums, target) {
	for(let x=0;x<nums.length;x++){
		let goal=target-nums[x];
		for(let y=x+1;y<=nums.length;y++){
			if(nums[y]===goal)
			    return [x,y];
        }
    }
}
//nums[]表示櫃子裡的考卷分數
//target表示小明的成績
//nums[x]小華的成績
//goal代表小明成績與小華成績相減的值，另一位他要嘲笑的同學
//x,y代表櫃子號碼

• 使用dictionaries概念

Map、 dictionaries、associative arrays、hashtable 都是一樣的概念，一種用key:value來表達關係的資料結構，就把他想像成key是書頁而value是內容，透過索引key來快速找到所要的值value，而不同程式語言有不同的實作方式。

又經過了一次期末考，白爛的小明又再次出動了，這次他考了70分，也一樣決定找兩位同學嘲笑。但是這次他學聰明了，先依序打開同學櫃子後，將同學的分數與櫃子號碼用表格紀錄下來。然後從第一個櫃子小華考了34分為基準，快速透過表格找到考26分的阿呆是在20號櫃子，快速將兩人考卷拿走。

//使用Map實作
let twoSum = function(nums, target) {
	let Mymap = new Map();
	for(let i=0;i<nums.length;i++){
	    Mymap.set(nums[i],i);
	}
	for(let x=0;x<nums.length;x++){
		let goal=target-nums[x];
	    if(Mymap.has(goal)&&x!=Mymap.get(goal))
	        return[x,Mymap.get(goal)];
    }
}
//將班上同學的成績與櫃子號碼用Ｍap紀錄
//直覺會想說要將櫃子號碼存在key，成績存value
//但是最後題目是要回傳櫃子號碼，因此將櫃子號碼放在value，之後方便get得到值
//set(key,value)將資料加入表格
//get(key)用key得到value
//x!=Mymap.get(goal)預防x數字重複使用

//使用Object實作
let twoSum = function(nums, target) {
	let dict={};
	for(let i=0;i<nums.length;i++){
	    dict[nums[i]]=i;
	}
	for(let x=0;x<nums.length;x++){
		let goal=target-nums[x];
	    if(goal in dict&&x!=dict[goal])
            return[x,dict[goal]];
	}
}
//將班上同學的成績與櫃子號碼用object紀錄
//直覺會想說要將櫃子號碼存在key，成績存value
//但是最後題目是要回傳櫃子號碼，因此將櫃子號碼放在value，之後方便得到值
//設定值dict[key]=value
//in用法是會看goal值有沒有出現在object的key過，有就回傳true
//x!=dict[goal]預防x數字重複使用

參考文章

• Map使用方式
• Object in使用方式

如果文章內容有任何問題或意見麻煩留言給我知道
感謝您